#include <bits/stdc++.h>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
};

// class Solution
// {
//   public:
//     ListNode *reverseBetween(ListNode *head, int left, int right)
//     {
//         // 创建虚拟头节点
//         ListNode *sen = new ListNode(0);
//         sen->next = head;
//         ListNode *p = sen;
//         // 找到第 left-1 个节点
//         for (int i = 0; i < left - 1; i++)
//         {
//             p = p->next;
//         }
//         ListNode *prv = nullptr;
//         ListNode *cur = p->next;
//         // 反转 left 到 right 之间的节点
//         for (int i = 0; i < right - left + 1; i++)
//         {
//             ListNode *nxt = cur->next;
//             cur->next = prv;
//             prv = cur;
//             cur = nxt;
//         }
//         // 连接反转后的链表
//         p->next->next = cur;
//         p->next = prv;
//         // 保存结果
//         ListNode *result = sen->next;
//         // 释放虚拟头节点的内存
//         delete sen;
//         return result;
//     }
// };

// class Solution
// {
//   public:
//     ListNode *reverseBetween(ListNode *head, int m, int n)
//     {
//         if (head == nullptr)
//             return nullptr;
//         ListNode *dummy = new ListNode(0);
//         dummy->next = head;
//         ListNode *p = dummy;
//         for (int i = 0; i < m - 1; i++)
//         {
//             p = p->next;
//         }
//         ListNode *cur = p->next;
//         ListNode *prev = nullptr;
//         for (int i = 0; i < n - m + 1; i++)
//         {
//             ListNode *nxt = cur->next;
//             cur->next = prev;
//             prev = cur;
//             cur = nxt;
//         }
//         p->next->next = cur;
//         p->next = prev;
//         ListNode *ans = dummy->next;//防止内存泄漏
//         delete dummy;
//         return ans;
//     }
// };